package gold.gold05;

/**
 * 重要。
 */
public class S1617连续数列 {
    /**
     * 92, 遇到很多次, 还是一头雾水。快慢指针, 总和为0放弃, 总和最大做记录。
     * 本题全负数情况返回负数。
     * 如果使用动态规划的想法来理解双指针, 比较方便。官方题解非常好, 要看。
     * 分治法需要多维护一个变量->区间所有元素之和。来处理跨区间问题。
     */
    public int maxSubArray(int[] nums) {
        if(nums.length <= 1) return nums.length == 0? 0: nums[0];
        int fast = 0;
        int max = nums[0];
        int sum = 0;
        for(int i: nums){
            sum += i;
            max = Math.max(sum, max);
            sum = sum > 0? sum: 0;
        }
        return max;
    }
    // 从题目提示的分治法出发试一下。
    // 返回左边开始的最大值, 右边开始的最大值, 中间的最大值。不行, 会连起来。
    // private int[] threeDiv(int[] nums){
    //     int len = nums.length;
    //     int[] res = new int[3];
    //     if(len == 1){
    //         if(nums[0]>0){
    //             Arrays.fill(res, nums[0]);
    //         }
    //         return res;
    //     }
    //     return null;
    // }

}
